Θ $\Theta$ -symbols (Asymptotically tight bound) Θ(g(n)) $\Theta(g(n))$ = { f(n) $f(n)$ :모든 n>n0 $n>n_0$ 에 대해 0≤c1g(n)≤f(n)≤c2g(n) $0\leq c_1g(n)\leq f(n)\leq c_2g(n)$ 인 양의 상수 c1,c2,n0 $c_1, c_2, n_0$ 이 존재한다.}

O $O$ -symbols (Asymptotically upper bound) O(g(n)) $O(g(n))$ = { f(n) $f(n)$ : 모든 n>n0 $n>n_0$ 에 대해 0≤f(n)≤cg(n) $0\leq f(n)\leq cg(n)$ 인 양의 상수 c,n0 $c, n_0$ 이 존재한다.

Ω $\Omega$ -symbols (Asymptotically lower bound) Ω(g(n)) $\Omega(g(n))$ = { f(n) $f(n)$ : 모든 n>n0 $n>n_0$ 에 대해 0≤cg(n)≤f(n) $0\leq cg(n)\leq f(n)$ 인 양의 상수 c,n0 $c, n_0$ 이 존재한다.

$f(n)=\Theta(g(n)) \leftrightarrow f(n)=O(g(n)$ , $f(n)=\Omega(g(n))$

o $o$ -symbols o(g(n)) $o(g(n))$ = { f(n) $f(n)$ : 임의의 양의 상수 c>0 $c>0$ 에 대해 그리고 모든 n≥n0 $n\geq n_0$ 에 대해 0≤f(n)≤cg(n) $0\leq f(n)\leq cg(n)$ 인 양의 상수 n0 $n_0$ 이 존재한다. limn→∞f(n)g(n)=0 $\lim_{n\to\infty}\frac{f(n)}{g(n)}=0$

ω $\omega$ -symbols ω(g(n)) $\omega(g(n))$ = { f(n) $f(n)$ : 임의의 양의 상수 c>0 $c>0$ 에 대해 그리고 모든 n≥n0 $n\geq n_0$ 에 대해 0≤cg(n)≤f(n) $0\leq cg(n)\leq f(n)$ 인 양의 상수 n0 $n_0$ 이 존재한다. limn→∞f(n)g(n)=∞ $\lim_{n\to\infty}\frac{f(n)}{g(n)}=\infty$

- 전이성

- 반사성

- 대칭성

- 역대칭성

- 삼분법

Asymptotic Effectivity